今天要討論的是集合覆蓋問題～概念其實跟昨天的旅行售貨員問題很相似喔！

集合覆蓋問題 (Set Cover)

有 N 個元素以及 M 個子集合，請你找出最少的子集合，使得每一個元素都出現在至少一個被挑選的子集合內。

直接上題吧！

Exercise 28: Leetcode 1125 - Smallest Sufficient Team

題目連結

https://leetcode.com/problems/smallest-sufficient-team/

題目敘述

現在給你一些必備技能列表，以及每個人到底會哪些技能。請你找出人數最少的隊伍，使得每一項列表上的技能該隊伍裡面都有人會。

解題思考

考慮任何技能列表的一個子集合 S，我們可以令 dp(S) 表示湊滿集合 S 的時候最少需要多少人（然後順便留下一個 list 表示一組解）。顯然 dp(空集合) = []。當我們找出 dp(S) 的時候，可以掃過所有人，試圖把這個人加進隊伍中，看看新的 dp(S+這個人會的東西) 當前的 list 會不會比較短，如果比較短的話就更新上去！這是一個主動式更新很好寫的例子！

參考程式碼 (Python3)

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        def get_mask(skill_list):
            return sum([2**req_skills.index(skill) for skill in skill_list])
        masks = [get_mask(skill_list) for skill_list in people]
        dp = {}
        dp[0] = []
        for state in range(0, 2**len(req_skills)):
            if dp.get(state) == None:
                continue
            for i, mask in enumerate(masks):
                if dp.get(state|mask) == None or len(dp[state|mask]) > len(dp[state]) + 1:
                    dp[state|mask] = dp[state] + [i]
        return dp[2**len(req_skills)-1]

動態規劃的主動式更新與被動式更新

• Push / 主動式更新就像今天這題，在計算小的問題時，主動將可能的答案推至下一個狀態。
• Pull / 被動式更新則像是傳統的遞迴表達式計算，等到真的要算這個值了，才去把它根據遞迴式實際計算出來。

我們可以用費氏數列的例子來講解 Push 和 Pull 的差別：

• Push 是在輪到 F(n) 的時候（陣列格子內已經有正確的 F(n) 值了），主動將 F(n) 的數值更新(加到) F(n+1) 和 F(n+2) 這兩個陣列格子。
• Pull 則是在輪到 F(n) 的時候，才去 F(n-1) 跟 F(n-2) 把數值拉出來，並且進行加總。

前幾天我們提到了良好定義動態規劃的狀態，可以得到很棒的執行效能。接下來我們要開始聊聊，在定義好動態規劃以後，如果有良好性質的話（比方說各種單調性），就可以用理論方式跳過許多不可能是最佳解的子問題，進而達到各種動態規劃的加速了～

嗯...先從 LIS 開始好了。